博弈论3 [推理与动态规划]

主题是推理与动态规划
由于是动态更新的,所以标号可能是乱的,不用在意标号问题,标号只是确定说之前更新到哪了
如果超过1515个题,就会专门再有一个传送门指向其他的文章.

①[POJ 1082] Calendar Game
原题链接:http://poj.org/problem?id=1082
题面就不放了,这题没啥意思,结论是月和天之和为偶数时先手必胜。但是很弱智的是有特例:9.309.3011.3011.30也是先手必胜。

②[POJ 2068] Nim
原题链接:http://poj.org/problem?id=2068
题目大意:有两个队伍,每个队伍有nn个人,你的队伍先手,即第一个人是你的队伍的人,且标号为11,并且两个队伍的人是交替坐成一个圈的。场上一共有SS个石头,每个人每次取的石头的数量最大值是MiM_i,且不能不取。问你的队伍是否必胜。
数据范围:
多组测试数据
1n101 \leq n \leq 10
1Mi161 \leq M_i \leq 16
1Si2131 \leq S_i \leq 2^{13}
样例输入:

1 101 4 4
1 100 4 4
3 97 8 7 6 5 4 3
0
0
1
1

这题看起来没什么性质可推,但是数据量由于人数非常小,可以考虑从原始定义出发:即从一个状态如果走到了一个必败态,则前者是必胜态;若走不到任何一个必败态则必败。用DPDP求解状态即可,整个局面是一个环,定义状态f[i][j]f[i][j]为当前是第ii个人,面对的局面是jj个石子在场上,若必胜为11,否则为00。状态的转移也比较好想,但是由于说涉及到环和取模,所以这里就使用记忆化以及求出去的状态的方式来做比较简单。具体来说当前的状态f[i][j]f[i][j]取决于当前取了xx个石块对应的后面一个状态f[(i+1)%(2n)][jx]f[(i + 1) \% (2 * n)][j - x]里有没有一个必败态,如果有的话就为11,如果遍历了所有的都没有,就是00。同时因为是一个环,所以为了方便代码的实现就把位置换成了从00开始而非从11开始、
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 22,M = 1 << 14;
int f[N][M];
int a[N],n,S;
bool dp(int i,int j)
{
	if(!j)	return 1;
	if(f[i][j] != -1)	return f[i][j];
	
	for(int k = 1;k <= a[i];++k)
	{
		if(j - k < 0)	break;
		if(dp((i + 1) % (2 * n),j - k) == 0)	return f[i][j] = 1;
	}	
	return f[i][j] = 0;
}
int main()
{
	while(scanf("%d",&n),n)
	{
		memset(f,-1,sizeof f);
		scanf("%d",&S);
		for(int i = 0;i < 2 * n;++i)	scanf("%d",&a[i]);
		if(dp(0,S))	puts("1");
		else puts("0");
	}
    return 0;
}

③[POJ 3668] Cheat in the game
原题链接:http://poj.org/problem?id=3688
题目大意:AliceBob在玩一个取石子游戏,一共有nn个卡片和最多mm个石头,每次两个人都会在nn张卡片中随机的选出一个,卡片上标记的数字就是本回合要取的石子数量,如果不够取就再抽一张,如果卡片抽完了胜者还没判别出来,则游戏重置再来,直到决出胜者为止。问在最多mm个石头的前提下,有多少种情况可以先手必胜。输出方案数即可。
数据范围:
多组测试数据
1n100001 \leq n \leq 10000
1m1000001 \leq m \leq 100000
1aim1 \leq a_i \leq m
样例输入:

3 8
1 5 7 
0 0

样例输出:

3

这个题的题意写得不够完整,注意卡片在抽出来了之后是不会反回去的,样例的合法数只有三个:1,5,71,5,7,并且先手必胜的判据是A的胜率是大于00,且B的胜率是00。虽然游戏可能进行很多次平局导致游戏重开,但是保证B的胜率是0就行了。
最简单也最直接的想法就是枚举所有石头的可能性,于是顺理成章的就想到了DPDP尝试一下看能不能把复杂度降下来。思考之后会发现DPDP也没法避免枚举,而且方法也不是很明确,说明题目还可能还有什么隐藏的判据没有找出来:
这个题目的选取的个数虽然表面上看是随机的,不过实际上,由于要保证B的胜率一定是00,所以说还是得考虑有可能的状态:即保证所有的情况下B都是必输的。因此,可以把“选择”这个条件去掉,变成“组合”,这个题最本质的性质就是:在所有情况中,一个数mm如果只能被奇数个数表示出来,那么他是必胜的,如果只能被偶数个数表示出来,那么他是必败的。其余的情况结局无法判明,但是至少不是必胜的。
因此DPDP就比较好想了:
第一步先要排序,使状态的更新是正确的。
状态:f[i][j]f[i][j]表示ii这个数,在j=1j=1时为能被偶数个数表示出来,j=0j=0时表示能被奇数个数表示出来。
入口:对于每个mim_i来说都有f[mi][0]=1f[m_i][0] = 1
出口:先手必胜的状态数就是满足f[i][0] == 1 && f[i][1] == 0的数,其中1m1 \leq m
转移:
j>mij > m_i,则有两种:
f[jmi][0]==1f[j - m_i][0] == 1时,f[j][1]=1f[j][1] = 1
f[jmi][1]==1f[j - m_i][1] == 1时,f[j][0]=1f[j][0] = 1

最后统计答案就可以了。

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e4+7,M = 1e5+7;
int a[N],f[M][2];
int n,m;
void dp()
{
	sort(a + 1,a + 1 + n);
	f[a[1]][0] = 1;
	for(int i = 2;i <= n;++i)
	{
		for(int j = m;j > a[i];--j)
		{
			if(f[j - a[i]][0])	f[j][1] = 1;
			if(f[j - a[i]][1])	f[j][0] = 1;
		}
		f[a[i]][0] = 1;
	}
}
int main()
{
	while(scanf("%d%d",&n,&m),n || m)
	{
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		memset(f,0,sizeof f);
		dp();
		int res = 0;
		for(int i = 1;i <= m;++i)
			if(f[i][0] && !f[i][1])	
				++res;
		printf("%d\n",res);
	}
    return 0;
}

④[POJ 1740]A New Stone Game
原题链接:http://poj.org/problem?id=1740
这题原题面写的很垃圾。
题目大意:AliceBob在玩一个新的石子游戏,一共有nn个石碓,每堆石子里不会超过有100100个石子。每次操作时,选择一个石碓,丢掉里面的一个石子,下一步可以不操作,也可以选出若干个石子放到另外一个当前非空的任意多个石碓里。最后一个拿走剩下所有石碓的人获胜。A先手,问是否先手必胜。
数据范围:
多组测试数据
1n101 \leq n \leq 10
样例输入:

3
2 1 3
2
1 1
0

样例输出:

1
0

这题是个规律题,nn一共也才1010个,可以枚举一下找结论:
n==1n == 1时,先手必胜
n==2n == 2时,如果两堆石子完全相同,则对手可以镜像操作,导致先手必败。除此之外先手必胜。
n==3n == 3时,先手把一堆石子全部拿空,可以变成n==2n == 2且相同的两堆的状态(是人为的构造两个不相同),因为可以任意分配到还有石子的堆里,所以是一定可以到达的。这样就构造了一个先手必败局面给对手,因此必胜。
n==4n==4时,同22可以拓展出一个结论:当nn为偶数的时候,如果石子可以两两分成两堆相同的组,就是先手必败的。同样,当nn是奇数是,可以构造出上一个偶数的状态,因此奇数是必胜的。
最后排个序验证一下结论就可以了。
代码:

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 20;
int n,a[N];
int main()
{
	while(scanf("%d",&n),n)
	{
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		sort(a + 1,a + 1 + n);
		if(n % 2)	printf("1\n");
		else
		{
			int ok = 1;
			for(int i = 1;i + 1 <= n;i += 2)
			{
				if(a[i] != a[i + 1])	
				{
					ok = 0;
					break;
				}
			}
			if(ok)	puts("0");
			else puts("1");
		}
	}
    return 0;
}